Today's cars are complex electromechanical systems. Despite their ever increasing technological complexity, there is much desire in improving the reliability of the electromechanical system. Consequently, the diagnosis process itself can become highly involved. For example, hardware systems and software systems together form a complex setup. In addition, data from various sensors is used by a complex network of distributed and inter-dependent software modules-modules that are specified at different phases in the development process and that are developed by different companies.
Classification of Fault Types
Errors and faults might occur at different places within a vehicle. As shown in FIG. 1, the system “vehicle” can be divided into two subsystems: the electronics and the environment. The electronics comprises the electronic control units (ECUs), the buses connecting ECUs, and the sensors and actuators which act as the ECU's interface to the environment. In today's cars up to seventy ECUs are connected to mechanical devices as well as to other ECUs and perform dedicated control tasks.
The main purpose of ECUs is to control parts of the environment, e.g., the engine or the gear. For this, ECUs execute application software modules. In addition to these software module applications, ECUs also contain basic software that is needed to execute applications and to connect them to sensors, actuators, and buses. The basic software comprises modules such as an operating system, I/O drivers, communication stack, and ECU services. Normally, the power supply is also included in the electronics subsystem.
The environment comprises the rest of the vehicle and includes the driver, the road, the weather, and the following vehicle domains:                Powertrain Examples: engine, gear, drive shaft        Chassis Examples: brakes, damping, steering        Body Examples: light, wipers, climate control, key-less entry        Safety Examples: airbag, active safety belts        Telematics/Infotainment Examples: radio, navigation, telephone        
FIG. 2 illustrates a sample taxonomy of fault locations. As mentioned previously, a vehicle can be subdivided into two main subsystems—the environment and the electronics. Within the environment subtree, the vehicle domains mentioned are differentiated as discussed above. In the electronics subtree, faults can occur in (i) ECUs, (ii) in connection with buses, (iii) in the context of the power supply, or (iv) in sensors, actuators, or their wiring. Note that within ECUs, both hardware and software can fail. The latter is often differentiated with respect to errors in application software or in basic software.
Diagnosis Based on Symptom Detection
The purpose of diagnosis systems within a vehicle is to identify faults and to initiate appropriate countermeasures. Fault identification suffers from one inherent problem: Faults can not be observed directly, and only the effects caused by the fault can be detected by the vehicle's electronics. For example, a fault in the engine may lead to unusual readings for sensors such as engine temperature or revolution (RPM).
In general, a diagnosis can be seen as a three step procedure:
1. Identification of unusual vehicle conditions. Such conditions are identified by comparing an expected vehicle behavior with the observed behavior—e.g. observed by means of sensor reading. Detected discrepancies are called symptoms.
2. Deduction of Faults. Based on the symptoms, the underlying faults are deduced.
3. Finally, countermeasures such as a warning to the driver are initiated by the diagnosis system.
Symptoms are detected in the software modules on the ECUs. FIG. 3 shows a simplified ECU structure from a software point-of-view. As illustrated in FIG. 3, an ECU is organized as different hardware and software layers. Faults may occur in each layer but do not become observable until the driver layer or the application layer.
Sensor readings or bus signals are read by application software modules via different hardware layers 100 and software layers 200 and are written to actuators or buses on hardware layer 300. In traditional diagnosis systems, symptom detection may only be implemented by drivers/basic software and by application software modules, i.e., all symptoms from all fault locations are detected by these software modules, rendering the process of differentiating between different faults a very difficult task.
Symptoms can be classified into two coarse categories, local and remote. Local symptoms occur directly at the fault's location. An example would be a short circuit of a cable attached to an ECU. Faults causing such kinds of local symptoms can be identified rather easily. In the example illustrated in FIG. 3, the corresponding I/O driver could detect the wrong voltage level.
Remote symptoms occur dislodged from the fault location. Examples of remote symptoms include (i) faults in the environment, e.g., engine problems or (ii) bus errors that influence all connected ECUs. Obviously, the detection of faults causing such symptoms is significantly more challenging.
Remote symptoms have occurred much more often in the last few years, leading to more and more difficult diagnosis scenarios. This is mainly due to the development towards more complex applications, i.e., towards large and distributed software systems. Examples of these systems include driver assistant functions such as active cruise control (ACC), active front steering (AFS), or the lane keeping support. These systems are distributed over several ECUs and often rely on other, already existing software modules. Faults occurring at one module of such a distributed software system may trigger further faults within other connected software modules. This leads to the detection of a large number of symptoms on several ECUs.
The diagnosis of technical systems is a research field that is largely governed by modeling questions:                Which modeling strategy is adequate, a deep behavior model or a shallow rule model?        Is a distinction between a correct behavior model and a fault model necessary?        Is the diagnosis process controlled by heuristic expert knowledge, and, if so, how shall it be represented?        How can diagnosis knowledge be maintained or kept up-to-date?        Is a modeling open to integrate knowledge of unforeseen faults?        
Traditional approaches predominantly use model-based diagnosis. The basic idea is to have a system simulation running in parallel to the real system and to use the simulation results to detect symptoms, i.e., discrepancies between the expected and observed behavior. This is referred to as a behavior model M.
In theory, possible faults causing symptoms can be deduced by analyzing a behavior model in reverse direction, from symptoms to faults. In practice, however, such an inverse simulation of M usually leads to a very complex analysis problem that is generally not traceable. Hence, often a specialized diagnosis model, MD, is constructed by domain experts, where fault deduction is treated in a forward reasoning manner.
Model-based approaches may employ different algorithms, as described in Raymond Reiter, ‘A Theory of Diagnosis from First Principles’, Artificial Intelligence, 32(1), 57-95, (1987) or Johan de Kleer and Brian C. Williams, ‘Diagnosing Multiple Faults’, Artificial Intelligence, 32(1), 97-130, (1987), which is hereby incorporated by reference as if set forth in its entirety. One approach for detecting failures during operation is described in Gerald Steinbauer and Franz Wotawa, “Detecting and locating faults in the control software of autonomous mobile robots” in IJCAI, pp. 1742-1743, (2005), which is hereby incorporated by reference as if set forth in its entirety. In these traditional systems, control software of autonomous robots is monitored with observers, which are a certain form of a behavior model running in parallel in order to detect symptoms. To find the faults, model-based diagnosis is applied. Here, the system's behavior, i.e., MD, is modeled using propositional logic. Reiter's hitting set algorithm, as discussed in Reiter and Russell Greiner, Barbara A. Smith, and Ralph W. Wilkerson, ‘A Correction to the Algorithm in Reiter's Theory of Diagnosis’, Artificial Intelligence, 41(1), 79-88, (1989), hereby incorporated by reference as if set forth in its entirety, is used together with a propositional Horn clause theorem prover. After the fault detection, an algorithm is executed which repairs the software.
In Sherif Abdelwahed, Gabor Karsai, and Gautam Biswas, ‘A Consistency-based Robust Diagnosis Approach for Temporal Causal Systems’, in 16th International Workshop on Principles of Diagnosis, DX-05, pp. 73-79, Monterey, Calif., USA, (June 2005), hereby incorporated by reference as if set forth in its entirety, a simple so-called “timed failure propagation graph” is introduced. This graph is used as M and indicates the way a failure propagates through the system. Additionally, the time range is known for the failure propagation between system components. Because of discrepancies between the expected behavior of a signal and the observed behavior, the faults detection is started. For this, the same graph is used, i.e. here M=MD.
In Tsoline Mikaelian, Brian C. Williams, and Martin Sachenbacher's ‘Diagnosing Complex Systems with Software-Extended Behavior using Constraint Optimization’, in 16th International Workshop on Principles of Diagnosis, DX-05, pp. 19-24, Monterey, Calif., USA, (June 2005), hereby incorporated by reference as if set forth in its entirety, systems comprising hardware and software are diagnosed. For this, a probabilistic, hierarchical, constraint-based automata is used as M and MD. The diagnosis task is formulated as a constraint optimization problem (COP) and solved with optimization techniques.
In Luca Console, Gerhard Friedrich, and Daniele Theseider Dupre's ‘Model-Based Diagnosis Meets Error Diagnosis in Logic Programs’, in IJCAI, pp. 1494-1501, Chambery, France, (1993), it was shown that model-based diagnosis can be applied to program debugging. As a result, many researchers started to work in this area, for example, as disused in Daniel Köb, Rong Chen, and Franz Wotawa, ‘Abstract model refinement for model-based program debugging’, in 16th International Workshop on Principles of Diagnosis, DX-05, pp. 7-12, Monterey, Calif., USA, (June 2005) (“Köb et al.); Irene Grosclaude, ‘Model-based monitoring of component-based software systems’, in 15th International Workshop on Principles of Diagnosis, DX-04, Carcassonne, France, (June 2004); and Wolfgang Mayer and Markus Stumptner, ‘Approximate Modeling for Debugging of Program Loops’, in 15th International Workshop on Principles of Diagnosis, DX-04, pp. 87-92, Carcassonne, France, (June 2004). In Köb et al. a technique similar to constraint propagation is used in combination with model checking. This technique depends on a model M=MD that is based on the source code. Component-based software is monitored in Grosclaude whereas the behavior of the software components is modeled by Petri nets, i.e., here M=MD. Symptoms are detected online. Each of these references is hereby incorporated by reference as if set forth in its entirety.
Furthermore, there exist approaches for detecting failures using distributed systems or multi-agent systems, as discussed in Indranil Roychoudhury, Gautam Biswas, Xenofon Koutsoukos, and Sherif Abdelwahed, ‘Designing Distributed Diagnosers for Complex Physical Systems’, in 16th International Workshop on Principles of Diagnosis, DX-05, pp. 31-36, Monterey, Calif., USA, (June 2005); James Kurien, Xenofon Koutsoukos, and Feng Zhao, ‘Disributed Diagnosis of Networked, Embedded Systems’, in 13th International Workshop on Principles of Diagnosis, DX-02, pp. 179-188, Semmering, Austria, (May 2002); R. Su, W. Wonham, J. Kurien, and X. Koutsoukos, ‘Distributed Diagnosis for qualitative Systems’, in Proceedings of the 6th International Workshop on Discrete Event Systems, WODES-02), eds., M. Silva, A. Giua, and J. M. Colom, pp. 169-174, Zaragoza, Spain, (October 2002); Nico Roos, Annette ten Teije, and Cees Witteveen, ‘A Protocol for Multi-Agent Diagnosis with spatially distributed Knowledge’, in Autonomous Agents and Multi Agent Systems, AAMAS-2003, pp. 655-661, (July 2003); Gianfranco Lamperti and Marina Zanella, Diagnosis of Active Systems, Kluwer Academic Publishers, Hingham, Mass., USA, 2003; and Meir Kalech and Gal A. Kaminka, ‘Towards Model-Based Diagnosis of Coordination Failures’, in 16th International Workshop on Principles of Diagnosis, DX-05, pp. 37-42, Monterey, Calif., USA, (June 2005). Each of these references is hereby incorporated by reference as if set forth in its entirety.
Diagnosis in Automotive Applications
In the automotive industry model-based approaches have also been used frequently. A main distinguishing feature is whether they are used onboard to diagnose failures during a vehicle's operation or if they are used offboard, e.g., in a garage. Legal requirements concerning gas emission and safety regulations, such as for driver assistant applications, demand more complex diagnosis systems for onboard diagnosis.
In Mattias Nyberg, ‘Model-based diagnosis of an automotive engine using several types of fault models’, IEEE Transaction on Control Systems Technology, 10(5), 679-689, (September 2002), which is hereby incorporated by reference as if set forth in its entirety, a no-fault-model M1=MD1 and various fault models M2=MD2 to Mk=MDk are constructed to diagnose sensor faults and leakages of the air-intake system of an engine. In the corresponding diagnosis system a framework of structured hypothesis tests is used to be able to decide which of the models can explain the measured data.
For many model-based approaches, qualitative models are used such as in Peter Struss and Chris Price, ‘Model-based systems in the automotive industry’, AI Magazine, 24(4), 17-34, (2004), hereby incorporated by reference as if set forth in its entirety, where consistency-based diagnosis is used for onboard diagnosis. In these approaches, there is used one model M=MD. Qualitative models, or more precisely qualitative deviation models, here M, for onboard diagnosis are also used in F. Cascio, L. Console, M. Guagliumi, M. Osella, A. Panati, S. Sottano and D. Dupre. On-board diagnosis of automotive systems: from dynamic qualitative diagnosis to decision trees, 1999, hereby incorporated by reference as if set forth in its entirety, where diagnostic situations are simulated. The outcome of the simulation is exploited to learn a decision tree for the diagnostic system. Some other model-based approaches are given in M. Sanseverino, F. Cascio, “Model-Based Diagnosis for Automotive Repair”, IEEE Expert, Vol. 12, No. 6, pp. 33-37 (1997); M. Fritz, A. Albers, “Fault detection in an electromechanical wheel brake actuator by model-based methods”, 2002; Werner Seibold and Bernhard Höfig, ‘Secure Diagnosis in the automotive maintenance with RODON 3, Vieweg, 2004; and in Frank Kimmich, Anselm Schwarte, and Rolf Isermann, ‘Fault detection for modern Diesel engines using signal- and process model-based methods’, Control Engineering Practice, 13(2), 189-203, (2005). Each of these references is hereby incorporated by reference as if set forth in its entirety.
The approach set forth in the present invention is based on the model compilation approach introduced in Benno Stein, Model Construction in Analysis and Synthesis Tasks, Habilitation, Department of Computer Science, University of Paderborn, Germany, June 2001, and in Uwe Husemeyer, Heuristic diagnosis with compound rules, Dissertation, University of Paderborn, Department of Mathematics and Computer Science, 2001. Each of these references is hereby incorporated by reference as if set forth in its entirety.